/*
 * @lc app=leetcode.cn id=37 lang=cpp
 *
 * [37] 解数独
 */

// @lc code=start
class Solution
{
private:
    bool isValid(int k, int row, int col, vector<vector<char>> &board)
    {
        // k为填的数字
        //一列中是否有重复的
        for (int i = 0; i < board.size(); i++)
        {
            if (board[i][col] - '0' == k)
            {
                return false;
            }
        }
        //一行中是否有重复的
        for (int i = 0; i < board[0].size(); i++)
        {
            if (board[row][i] - '0' == k)
            {
                return false;
            }
        }
        // 3x3的方块有无重复
        //首先寻找该方格属于哪个大方块
        //显然大方格的中心点位置为[3i-2,3j-2]
        //不对 为了遍历方便应该寻找左下角的点
        int row_1 = row / 3;
        int col_1 = col / 3;

        int r = 3 * row_1;
        int c = 3 * col_1;
        for (int i = r; i < r + 3; i++)
        {
            for (int j = c; j < c + 3; j++)
            {
                if (board[i][j] - '0' == k)
                {
                    return false;
                }
            }
        }

        return true;
    }
    bool backtracking(vector<vector<char>> &board)
    {
        //终止条件 其实不需要 因为找到解后直接返回了 不需要停止
        for (int i = 0; i < board.size(); i++)
        {
            for (int j = 0; j < board[0].size(); j++)
            {
                if (board[i][j] != '.')
                {
                    continue;
                }
                //尝试1-9数字是否可以
                for (int k = 1; k < 10; k++)
                {
                    if (isValid(k, i, j, board))
                    {
                        char tmp = k + '0';
                        board[i][j] = tmp;
                        if (backtracking(board))
                        {
                            return true;
                        }
                        board[i][j] = '.';
                    }
                }
                //如果9个数字都不行直接返回false
                return false;
            }
        }
        return true; //最后全部填满
    }

public:
    void solveSudoku(vector<vector<char>> &board)
    {
        //解数独 回溯法
        //限制条件是行 列  以及3x3的小方格都不能重复
        //类似n皇后 但是明显更复杂一些
        //如果是单层递归的话 比如n皇后每层只选一个可以
        //但是这里每一层需要填多个数字
        //所以直接遍历所有位置
        backtracking(board);
    }
};
// @lc code=end
